Packet switching communication networks such as those based upon Asynchronous Transfer Mode (ATM) technology are increasingly used to transfer digital information over long distances. A typical ATM network can be viewed as including several different types of elements that permit an end node or user node such as a personal computer (PC) to be connected to other digital terminal equipment (DTE) such as host computer or service provider node. ATM networks transfer data in fixed length packets or "cells" on a demand driven basis using virtual paths and virtual channels defined within a physical transmission medium.
With the recent explosive growth in Internet-related data traffic, network service providers (NSPs) have had to find new ways to quickly upgrade their own network facilities to alleviate congestion and bottlenecks. The NSPs have therefore begun to deploy ATM technology in the core or background of their networks as an efficient and flexible means of carrying large amounts of data traffic. ATM is also being deployed towards the edge or access side of the network where it may provide connections to access multiplexers or so-called access nodes that allow residential users to connect to Internet Service Providers (ISPs) through an ATM network.
The elements within an ATM network include devices known as an access node and a switching node. The access node, more formally called a service access multiplexer, allows the combination of a variety of lower speed service connections into a single higher speed connection. The switch nodes may thus use higher speed communication links to move cell traffic to its intended destination. For example, an access node may aggregate traffic on multiple low speed links such as T1 or xDSL type digital communication links, and provide a connection to a switching node via high speed trunk lines such as T3 or OC3 communication links.
In general, it is desired that the trunk lines connected between the access nodes and the switching network only require a traffic capacity which is sufficiently large enough to handle the average expected load but not necessarily a peak expected load. The access nodes therefore preferably also perform some type of statistical multiplexing function. The statistical multiplexing function can, for example, operate on the cells on a first-in and first-out basis. In other words, the next cell to be sent over the trunk line can be selected to be the cell which entered the access node first.
Any mechanism used for selecting the cell priority needs to be fair and nonblocking in order for most applications, such as transaction processing, voice over cell and/or cell aggregation schemes for multiple users, to operate properly. In practice, first-in first-out queuing alone has been unable to provide the characteristics expected of an ATM network. It is, therefore, also often desirable in such networks for some sort of priority access to be granted to certain cells.
One priority scheme has been to try to equalize the bandwidth allocated per user node. Another approach is to prioritize access to the trunk based upon traffic loading. In this scenario, priority is granted on a dynamic basis to the nodes which have the higher amount of traffic.
Implementing any sort of priority scheme in this situation is complicated by the fact that ATM itself is a type of multiplex scheme. In particular, ATM was originally conceived as a flexible and responsive method for supporting multiple forms of digital traffic, including data, voice, image, and video, while providing rapid adaptability to changes in patterns of network traffic. The users of ATM networks generally expect that a mixture of bursty and delay sensitive traffic can be processed simultaneously.
ATM contrasts with more traditional multiplexing methods in the way in which it allocates communication channels. In traditional time division multiplexing, for example, communication channel access is divided into fixed periods of time called "frames." Frames are then divided into a fixed number of time slots of equal duration. Each user is then assigned a certain time slot within each frame. The time slots are generally implemented in a manner which is synchronous. A user node can therefore access a communication channel only during the time slot that has been allocated to them. If no traffic is ready to send when the designated time slot occurs, then the time slot is unused.
In contrast to this, in an ATM network, access to the communication channel is more flexible. Any user needing to communicate can use the channel whenever it is available. Therefore, ATM imposes no regular pattern on the way users are given access to a communication channel. In order to avoid a situation where any given user would monopolize the channel, every message is divided into small, fixed length cells. Arrangements are then made in the switching fabric such that no single user can monopolize access to the communication channel while other users have messages to send.
Any arbitration scheme for an access node to be used together with an ATM network therefore should exhibit priority allocation properties that are consistent with the overall ATM architectural philosophy. Otherwise, the access node itself may restrict the benefits obtainable by using ATM in the first place.
It is also useful to have a system that can be used to distribute the cell bus control mechanism over multiple cell queues with no central entity making the decision as to which cell is to be transmitted. This would have many advantages, including lower cost, better fault tolerance, improved scalability, and ease of hardware implementation.